;; The first three lines of this file were inserted by DrRacket. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname reachables-wed) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ())))
(require rackunit)
(require "extras.rkt")

;; Node = Int


;; Int -> SetOfInt
;; GIVEN: an integer
;; RETURNS: the list of its successors in the implicit graph.
;; For this graph, this is always a set (no repetitions)
(define (successors1 n)
  (if (<= n 0) 
      empty
      (local
        ((define n1 (quotient n 3)))
        (list n1 (+ n1 5)))))

(begin-for-test
  (check set-equal? (successors1 6) (list 2 7))
  (check set-equal? (successors1 2) (list 0 5))
  (check set-equal? (successors1 0) empty)
  (check set-equal? (successors1 5) (list 1 6))
  (check set-equal? (successors1 1) (list 0 5)))

(define (all-successors nodes)
  (foldr
    (lambda (node ans-for-rest)
      (set-union
        (successors1 node)
        ans-for-rest))
    empty
    nodes))

(begin-for-test
  (check set-equal?
    (all-successors (list 2 6))
    (list 0 5 2 7)))

;; reachable-in : Node Nat -> SetofNode
;; GIVEN: A node s and a nonnegint n,
;; RETURNS: the set of nodes reachable from s
;; in at most n steps.
;; STRATEGY: general recursion
;; HALTING MEASURE: n
(define (reachable-in s n)
  (if
   (zero? n) 
   (list s)
   (local
     ((define already-seen (reachable-in s (- n 1))))
     (set-union
      already-seen
      (all-successors already-seen)))))



;; reachable : Node SetofNode -> SetOfNode
;; GIVEN: a node s and a set seen
;; WHERE: there are only a finite number of nodes
;;  reachable from s
;; AND seen = (reachable-in s n) for some n.
;; RETURNS: the set of all nodes reachable from s.
;; STRATEGY: General Recursion
;; HALTING MEASURE: (# of nodes reachable from s) - (# of nodes in seen)
(define (reachable s seen)
  (local
    ((define new-nodes 
       (set-union
        seen
        (all-successors seen))))
    (if
     (set-equal? seen new-nodes)
     seen
     (reachable s new-nodes))))

;; reachable-nodes : Node  -> SetOfNode
;; GIVEN: a node s
;; WHERE: there are only a finite number of nodes
;;  reachable from s
;; RETURNS: the set of all nodes reachable from s.
;; STRATEGY: FUNCTION COMPOSITION
;; initialize the invariant.
(define (reachable-nodes s)
  (reachable s (list s))







#;(begin-for-test
  (check set-equal? (reachable (list 30) 0)
         (list 30))
  (check set-equal? (reachable (list 30) 1)
         (list 30 10 15))
  (check set-equal? (reachable (list 30) 2)
         (list 30 10 15 3 8 5)))